package cn.zhangchg.leetcode.arrays;

import java.util.*;

/**
 * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
 * <p>
 * 注意：
 * <p>
 * 答案中不可以包含重复的四元组。
 * <p>
 * 示例：
 * <p>
 * 给定数组 nums = [1, 0, 1, 0, 2, 2]，和 target = 0。
 * <p>
 * 满足要求的四元组集合为：
 * [
 * [1,  0, 0, 1],
 * [2, 1, 1, 2],
 * [2,  0, 0, 2]
 * ]
 *
 * @author 张晨刚
 */
public class FindKNumber {

    public static void main(String[] args) {
        //System.err.println(findKth(new int[]{1, 3, 1, 5, 1, 4}, 2));
        System.err.println(findKth(new int[]{1, 3, 1, 3, 2, 2}, 3));
        System.err.println(findKth(new int[]{5, 5, 3, 5, 1, 5, 1, 2}, 4));
        System.err.println(findKth(new int[]{3, 3, 3, 3}, 3));
        System.err.println(findKth(new int[]{1, 3, 1, 2, 1, 4}, 1));
        System.err.println(findKth(new int[]{3, 1, 5, 3, 1, 5, 5, 4}, 11));
        System.err.println(findKth(new int[]{5, 4, 2, 2, 2, 1, 3, 3, 1}, 5));
        System.err.println(findKth(new int[]{1, 3, 1, 2, 1, 4}, 2));
        System.err.println(findKth(new int[]{1, 5, 3, 1}, 2));
        System.err.println(findKth(new int[]{1, 3, 1, 7}, 2));
        System.err.println(findKth(new int[]{3, 1, 5}, 2));
    }

    public static int findKth(int[] arr, int k) {
        int[] result = new int[k];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 == 0) {
                continue;
            }
            insert(result, arr[i]);
        }
        return result[result.length - 1];
    }

    private static boolean insert(int[] result, int num) {
        if (result[result.length - 1] != 0 && num >= result[result.length - 1]) {
            return false;
        }
        for (int i = 0; i < result.length; i++) {
            if (result[i] <= 0) {
                result[i] = num;
                break;
            }
            if (result[i] < num) {
                continue;
            }
            int flag = result[i];
            result[i] = num;
            num = flag;
        }
        return true;
    }

}
